package com.yequan.leetcode.recursion.canmeasurewater;

/**
 * //有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
 * //
 * // 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
 * //
 * // 你允许：
 * //
 * //
 * // 装满任意一个水壶
 * // 清空任意一个水壶
 * // 从一个水壶向另外一个水壶倒水，直到装满或者倒空
 * //
 * //
 * // 示例 1: (From the famous "Die Hard" example)
 * //
 * // 输入: x = 3, y = 5, z = 4
 * //输出: True
 * //
 * //
 * // 示例 2:
 * //
 * // 输入: x = 2, y = 6, z = 5
 * //输出: False
 * //
 * // Related Topics 数学
 *
 * @author : Administrator
 * @date : 2020/3/21
 */
public class CanMeasureWater {

    public static void main(String[] args) {
        int x1 = 3, y1 = 5, z1 = 4;
        int x2 = 2, y2 = 6, z2 = 5;
        CanMeasureWater canMeasureWater = new CanMeasureWater();
        System.out.println(canMeasureWater.canMeasureWater(x1, y1, z1));
        System.out.println(canMeasureWater.canMeasureWater(x2, y2, z2));
    }

    public boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) {
            return false;
        }
        if (x == 0 || y == 0) {
            return z == 0 || x + y == z;
        }
        return z % getGCD(x, y) == 0;

    }

    /**
     * 穷举法求最大公约数
     * 1.找出两数中较小的一个
     * 2.然后从穷举最小数次,两数同时取模,同时为0则记录,直到结束
     *
     * @param num1
     * @param num2
     * @return
     */
    public int getGCD(int num1, int num2) {
        // 先获得绝对值，保证负数也可以求
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        // 找到小的那个数
        int min = Math.min(num1, num2);
        // 初始最大公约数为 1
        int gcd = 1;
        // 穷举, 直接从 2 开始
        for (int i = 2; i <= min; i++) {
            // 如果 i 能被两个数同时约分，则是它们的公约数，但不一定是最大的
            if (num1 % i == 0 && num2 % i == 0) {
                // gcd 从最小的公约数，一直到最大的公约数
                gcd = i;
            }
        } // for
        return gcd;
    }

}
